\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{url}
\usepackage{framed, color}
\definecolor{shadecolor}{rgb}{1,1,1}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{color}
\usepackage{listings}
\lstset{ %
language=R,                % choose the language of the code
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
stepnumber=1,                   % the step between two line-numbers. If it is 1 each line will be numbered
numbersep=7pt,                  % how far the line-numbers are from the code
backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,           % adds a frame around the code
tabsize=2,          % sets default tabsize to 2 spaces
captionpos=b,           % sets the caption-position to bottom
breaklines=true,        % sets automatic line breaking
breakatwhitespace=false,    % sets if automatic breaks should only happen at whitespace
escapeinside={\%*}{*)},          % if you want to add a comment within your code
xleftmargin=.5in,
xrightmargin=.25in
}

\title{Week 5: Recursion in programming, cognition and networks}
\author{Willem Zuidema, Phong Le}

\begin{document}
\lstset{language=R}
\renewcommand{\lstlistingname}{Code}

\maketitle

\section{Functions}
\label{section functions}

Over the last few weeks we have seen examples of functions that are
built-in in R, as well as a number of scripts that defined new
functions. Functions are the building blocks of computer programs -
the bits of code that we give a separate name so that we can reuse
them again and again. Today, we are going to define some new functions
ourselves.

The structure of a function is given as follows
\begin{lstlisting}
func_name <- function(arg1, arg2, ...) {
    statement
    return(output)
}
\end{lstlisting}
where \texttt{func\_name} is the function's name; \texttt{arg1}, \texttt{arg2}, etc. 
are the function's arguments (i.e., function's inputs); and \texttt{return(output)}
is to claim that the output of the function is the object \texttt{output}, which 
need to be declared in the body of the function (i.e., \texttt{statement}). 

\begin{framed}
Exercise \ref{section functions}.1: Write a function \texttt{sigmoid} that, for a given $x$ calculates the $y$ value. Recall that the sigmoid function is defined as:
\[
y = \frac{1}{1+e^{-x}}
\]

Check that the function works equally well with $x$ a scalar (a single value of x) as with $x$ a vector.
Plot the function with:
\begin{lstlisting}
x <- seq(-5,5,by=0.1)           # create x = (-5,-4.9,-4.8,...,4.9,5)
y <- sigmoid(x)                     # compute y values
plot(x,y,type='l',col='blue')   # draw the graph, using blue color
\end{lstlisting}

\end{framed}

\section{Scripts}
\label{section scripts}
Programming directly in an R console is a bad idea because we can't
bring our programs to another computer. Therefore, we should store our
source code in a file and execute it anytime we want by the function
\texttt{source("file\_path")}.

\begin{framed}
Exercise \ref{section scripts}.1: Store your code in Exercise
\ref{section functions}.1 in a file ``sigmoid.r'' and execute it by
typing \texttt{source("sigmoid.r")} in an R console.  (If the error
``cannot open file'' occurs, you change your working directory.)
\end{framed}

\section{Control Structures}
\label{section control structures}

\subsection{Conditional Execution}
Think about what would happen if our languages lack the words `if', `else', 
`otherwise', etc.  and you will see why any programming language has to have 
conditional execution. In R, conditional execution is given by the following 
structure
\begin{lstlisting}
if (condition) {
    statement
} else {
    alternative
}
\end{lstlisting}
The \textit{condition} is a logical expression which may contain one of the following
operations
\begin{itemize}
    \item $x == y$ ``$x$ is equal to $y$''
    \item $x != y$ ``$x$ is not equal to $y$''
    \item $x > y$ ``$x$ is greater than $y$''
    \item $x < y$ ``$x$ is less than $y$''
    \item $x <= y$ ``$x$ is less than or equal to $y$''
    \item $x >= y$ ``$x$ is greater than or equal to $y$''
\end{itemize}
or a combination of those using the \& or \&\& operators for AND, $|$ or $||$ are the 
operators for OR.

For instance, the following code will let us know, when we flip two fair coins, whether 
the results are both `head'
\begin{lstlisting}
x <- runif(2)   # flip two fair coins
print(x)
# suppose that "> 0.5" means "head"
# we check if BOTH two values > 0.5 or not
if (x[1] > 0.5 && x[2] > 0.5) {
    # both > 0.5
    print("bingo!!!")
} else {  
    # at least one of them <= 0.5
    print("boooo!!!")
}
\end{lstlisting}
(Note: the ``else'' part is not necessary, you can omit it freely if you have nothing 
to do with it.)

\begin{framed}
Exercise \ref{section control structures}.1: Modify the code above to check whether 
at least one result is `head'.
\end{framed}

\subsection{Loops}
Suppose that we have a fair coin, and we flip it 1000 times and count how many times
the coin turns head. To do that, we use the \texttt{for} statement like this way:
\begin{lstlisting}[caption=Using the \texttt{for} loop to count how many times 
a fain coin turns head., label=code for]
x <- runif(1000)   # flip a fair coin 1000 times
count <- 0
# suppose that "> 0.5" means "head"
# note that 1:1000 creates an array (1,2,3,...,1000)
for (i in 1:1000) {
    if (x[i] > 0.5) {
        count <- count + 1
    }
}
print(count)
\end{lstlisting}
%
The \texttt{for} loop above iterates each element in the array
(1,2,...,1000).  Firstly, the first element is assigned to $i$, and
hence we check the value $x[1]$: if $x[1] > 0.5$ then we increase the
$count$ by 1. Then, the second element is assigned to $i$, and hence
we check the value $x[2]$.  And so on until the last element is
assigned to $i$, and hence we check the value $x[10000]$.

We can wrap Code~\ref{code for} into a function like this
\begin{lstlisting}
# function count_head
# input: num_of_flips is a number of times we flip the coin
# output: the number of times the coin turns head
count_head <- function(num_of_flips) {
    x <- runif(num_of_flips)   # flip a fair coin 
    count <- 0
    for (i in 1:num_of_flips) {
        if (x[i] > 0.5) {
            count <- count + 1
        }
    }
    return(count)
}
\end{lstlisting}
Now, to flip a fair coin 10000 times and count how many times it turns head, 
we simply execute \texttt{count <- count\_head(10000)} (instead of typing 
Code~\ref{code for} again and again each time we need to perform the task).

\section{Recursion}
\label{recursion}

R also allows us to write recursive functions: functions that call
themselves! This can be extremely useful, but should be handled with
care. Recursive functions always have (at least) two parts: a
stop-condition (to avoid infinite loops) and a recursive step.  As an
easy example, consider a function \texttt{mysum} that sums all
elements from row $r1$ until row $r2$ in a vector $x$ (of course, we could
easily do that with the built-in function \texttt{sum()}, or write our
own function with a for-loop, but a recursive solution is more fun):
\[
mysum(x,r1,r2) = \left\{ \begin{array}{cl} x[r1] & if (r1==r2)\\
x[r1] + mysum(x,r1+1,r2) & otherwise
  \end{array} \right.
\]

\begin{framed}
Exercise \ref{recursion}.1: Implement this function in R, and test it
on some example vectors.
\end{framed}

We can use recursive function also to generate strings, using the
framework of formal grammars. For instance, we can generate the formal
language $(ab)^n$ with the function below (that uses the built-in function \texttt{cat} to print characters on the screen):

\begin{lstlisting}
 abn <- function(n) {
   if (n==1) cat("ab")
   else {
     cat("a")
     cat("b")
     abn(n-1)
   }
 }
\end{lstlisting}

\begin{framed}
Exercise \ref{recursion}.2: Generate some string with this function
for randomly chosen $n$'s.
\end{framed}

\begin{framed}
Exercise \ref{recursion}.3: Write a recursive function to generate strings from $a^nb^n$.
\end{framed}

\section{Recurrent networks}

\begin{itemize}
\item Write a recursive function that implements the forward sweep of a multilayer perceptron given a connectivity matrix
\item Change the connectivity matrix such that it becomes a simple recurrent network
\item Write a recursive function that feeds all rows of a matrix to a simple recurrent network
\item Design a connectivity matrix that implements $a^nb^n$
\item Write a recursive function that solves tower-to-tower Tower of Hanoi problems
\end{itemize}

%\begin{framed}
%Exercise \ref{section functions}.2 (***): Wrap your code in Exercise 
%\ref{section graphics}.2 in a function such that we can do the same thing
%with any sampling function and any density function. (Hint: an input to
%a function can be a function.)
%\end{framed}

%\paragraph{Variable Scope} You are strongly recommended to understand variable
%scope in R, which is presented at 
%\url{http://cran.r-project.org/doc/manuals/R-intro.html\#Scope}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Submission}
You have to submit a file named `your\_name.pdf'.
%for those exercises requiring explanations and math solutions


\appendix


\section{More control structures}

Suppose we want to flip the coin until it turns head. We can't use the
\texttt{for} statement because we don't know how many times we need to
flip the coin. Here, we need another loop statement, namely
\texttt{while}:
\begin{lstlisting}
while (condition) {
    statement
}
\end{lstlisting}
The \texttt{while} loop will execute the \texttt{statement} as long as the 
\texttt{condition} is correct (i.e., \texttt{TRUE}). Therefore, our problem 
is solved by the following code
\begin{lstlisting}
# suppose that "> 0.5" means "head"
x <- runif(1)   # flip the coin
print(x)
while (x <= 0.5) {
    x <- runif(1)   # flip the coin
    print(x)
}
print("bingo!!!")
\end{lstlisting}

%\begin{framed}
%Exercise \ref{appendix}.1: 
%\begin{itemize}
%    \item Interpret the code above in your own words.
%    \item Modify the code above using \texttt{repeat} (another loop statement).
%\end{itemize}
%\end{framed}

\section{Indexing}
\label{indexing}

We can get an element by using the operator \texttt{[]}. For instance, 
\texttt{vec[i]} points to the i-th element of a vector \texttt{vec}, 
\texttt{mat[i,j]} points to the element on the i-th row, the j-th column 
of a matrix \texttt{mat}.

The operator \texttt{[]} can do further than that: we can get a set of elements.
For instance, \texttt{a[c(1,3)]} and \texttt{a[c(TRUE,FALSE,TRUE)]} 
point to the first and the third elements of vector \texttt{a};
\texttt{A[1,c(2,3)]} and \texttt{A[1,c(FALSE,TRUE,TRUE)]} point to the second 
and the third elements on the first row of matrix \texttt{A}, 
and \texttt{A[,2]} points to the second column.
%(Check those yourself with \texttt{a} and \texttt{A} given above.)

%\begin{framed}
%Exercise \ref{appendix}.2: 
%\begin{itemize}
%    \item Use the operator \texttt{[]} to confirm that \texttt{C} is a magic square. 
%    (Hint: use \texttt{sum} to compute the sum of all elements of a vector.)
%    
%    \item Find all positive elements in \texttt{a}. (Hint: use \texttt{a > 0}.)
%    
%    \item Find the sum of the all negative elements in \texttt{B}.
%\end{itemize}
%\end{framed}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%% \paragraph{Loops are \textit{expensive} and we should avoid using them whenever we can!!!}
%% In order to see that, let's run the following code, which measures the execution time 
%% of two methods computing the sum of the all elements of a vector
%% \begin{lstlisting}
%% n <- 1000000
%% x <- runif(n)   # create an n-element vector
%% sum <- 0
    
%% # the first method: using for loop
%% ptm <- proc.time()          # start clock
%% for (i in 1:n) {
%%     sum <- sum + x[i]
%% }
%% print(sum)
%% print(proc.time() - ptm)    # stop clock

%% # the second method: using the built-in function sum()
%% ptm <- proc.time()
%% print(sum(x))
%% print(proc.time() - ptm)
%% \end{lstlisting}
%% You should get an output like this (note that the numbers you get should be slightly 
%% different due to the sampling process as well as your computer power)
%% \indent \begin{lstlisting}
%% [1] 500109.2
%%     user  system elapsed 
%%     1.308   0.000   1.311 
%% [1] 500109.2
%%     user  system elapsed 
%%     0.004   0.000   0.003 
%% \end{lstlisting}
%% which tells us that the two methods return the same result but with very different
%% execution time: the second clearly run much much (327 times) faster than the other.

%% \begin{framed}
%% Exercise \ref{section control structures}.3: How can you avoid using the \texttt{for}
%% loop in Code~\ref{code for}? Implement your idea. (Hint: use \texttt{x > 0.5}.)
%% \end{framed}


%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%% \section{Practical issues}
%% \subsection{What should you do when you get stuck?}
%% \paragraph{Google your problem!} R is widely used, and its user community is very large.
%% Therefore, you can easily find someone that had the same problem and successfully
%% solved it. For instance,
%% \begin{figure}[h!]
%%     \centering
%%     \includegraphics[width=0.8\textwidth]{can_not_open_file.png}
%% \end{figure}
%% \begin{figure}[h!]
%%     \centering
%%     \includegraphics[width=0.8\textwidth]{sum.png}
%% \end{figure}

%% If you can't find any solution on the Internet, posting your problem on the course 
%% forum.

\end{document}
